#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution {
private:
    vector<int> ans;
    vector<int> get_sub(vector<int>& nums, int k) {
        stack<int> stack;
        for (int i = 0; i < nums.size(); i++) {
            while (stack.size() > 0 && nums[i] > stack.top() && nums.size() - 1 - i >= k - stack.size()) {
                stack.pop();
            }
            if (stack.size() < k) {
                stack.push(nums[i]);
            }
        }
        vector<int> ans(stack.size());
        for (int i = stack.size() - 1; i >= 0; i--) {
            ans[i] = stack.top();
            stack.pop();
        }
        return ans;
    }
    void merge(vector<int> nums1, vector<int> nums2) {
        int ptr[2] = {0, 0};
        vector<int> ans(nums1.size() + nums2.size());
        for (int i = 0, len = nums1.size() + nums2.size(); i < len; i++) {
            if (ptr[0] == nums1.size()) {
                ans[i] = nums2[ptr[1]];
                ptr[1]++;
            } else if (ptr[1] == nums2.size()) {
                ans[i] = nums1[ptr[0]];
                ptr[0]++;
            } else if (nums1[ptr[0]] > nums2[ptr[1]]) {
                ans[i] = nums1[ptr[0]];
                ptr[0]++;
            } else if (nums1[ptr[0]] < nums2[ptr[1]]){
                ans[i] = nums2[ptr[1]];
                ptr[1]++;
            } else {
                if (cmp(nums1, nums2, ptr[0], ptr[1])) {
                    ans[i] = nums1[ptr[0]];
                    ptr[0]++;
                } else {
                    ans[i] = nums2[ptr[1]];
                    ptr[1]++;
                }
            }
        }
        if (cmp(ans)) {
            this->ans.assign(ans.begin(), ans.end());
        }
    }
    bool cmp(vector<int> nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > ans[i]) {
                return true;
            } else if (nums[i] < ans[i]) {
                return false;
            }
        }
        return false;
    }
    bool cmp(vector<int> nums1, vector<int> nums2, int i1, int i2) {
        for (; i1 < nums1.size() && i2 < nums2.size(); i1++, i2++) {
            if (nums1[i1] > nums2[i2]) {
                return true;
            } else if (nums1[i1] < nums2[i2]) {
                return false;
            }
        }
        return nums1.size() - i1 > nums2.size() - i2;
    }
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        ans.assign(k, 0);
        int max_k1 = min((int) nums1.size(), k);
        for (int k1 = 0; k1 <= max_k1; k1++) {
            int k2 = k - k1;
            if (k2 > nums2.size()) {
                continue;
            }
            vector<int> sub1 = get_sub(nums1, k1);
            vector<int> sub2 = get_sub(nums2, k2);
            merge(sub1, sub2);
        }
        return ans;
    }
};

int main() {
    vector<int> input1 = {6,3,9,0,5,6};
    vector<int> input2 = {2,2,5,2,1,4,4,5,7,8,9,3,1,6,9,7,0};
    Solution solution;
    vector<int> output = solution.maxNumber(input1, input2, 23);
    for (int num : output) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}